/*
定义邻接矩阵的图的基本操作
*/

#include <iostream>
using namespace std;

template <typename T>
T** init2DArray(int n, int m) {
    T* temp = new T[n * m];
    T **array = new T*[n];
    for (int i = 0; i < n; i++) {
        array[i] = temp + i * m;
    }
    return array;
}

template <typename T>
T** init2DArray(int n) {
    return init2DArray<T>(n, n);
}

template <typename T>
void free2DArray(T **array, int n) {
    delete[] array[0];
    delete[] array;
}

template <typename T, typename TWeight>
class MGraph {
public:
    MGraph(int num_vertex, TWeight no_edge_value = 0, bool directed = false) {
        this->num_vertex = num_vertex + 1;
        this->num_edge = 0;
        this->vertex = new T[this->num_vertex];
        this->no_edge_value = no_edge_value;
        this->directed = directed;
        this->edge = init2DArray<TWeight>(this->num_vertex);
        for (int i = 0; i < this->num_vertex; i++) {
            this->edge[i] = new TWeight[this->num_vertex];
            for (int j = 0; j < this->num_vertex; j++) {
                this->edge[i][j] = this->no_edge_value;
            }
        }
    }

    ~MGraph() {
        delete[] vertex;
        free2DArray(edge, num_vertex);
    }

    void set_edge(int i, int j, TWeight weight) {
        edge[i][j] = weight;
        if (!directed) {
            edge[j][i] = weight;
        }
    }

    void add_edge(int i, int j, TWeight weight = 1) {
        edge[i][j] = weight;
        if (!directed) {
            edge[j][i] = weight;
        }
        num_edge++;
    }

    void remove_edge(int i, int j) {
        edge[i][j] = 0;
        if (!directed) {
            edge[j][i] = this->no_edge_value;
        }
        num_edge--;
    }

    TWeight get_edge(int i, int j) const {
        return edge[i][j];
    }

    bool has_edge(int i, int j) const {
        return edge[i][j] != this->no_edge_value;
    }

    int get_num_vertex() const {
        return num_vertex;
    }

    int get_num_edge() const {
        return num_edge;
    }

    T get_vertex(int i) const {
        return vertex[i];
    }

    void set_vertex(int i, T value) {
        vertex[i] = value;
    }

    // 输入邻接矩阵，无权图
    void inputWithoutWeight(int num_edge) {
        int u, v;
        for (int i = 0; i < num_edge; i++) {
            cin >> u >> v;
            add_edge(u, v);
        }
    }

    // 输入邻接矩阵，有权图
    void inputWithWeight(int num_edge) {
        int u, v;
        TWeight w;
        for (int i = 0; i < num_edge; i++) {
            cin >> u >> v >> w;
            add_edge(u, v, w);
        }
    }

    void print() const {
        cout << "Graph, vertex: " << num_vertex << ", edge: " << num_edge << endl;
        for (int i = 0; i < num_vertex; i++) {
            // cout << vertex[i] << ": ";
            for (int j = 0; j < num_vertex; j++) {
                if (edge[i][j] != this->no_edge_value) {
                    // cout << vertex[j] << "(" << edge[i][j] << ") ";
                    cout << edge[i][j] << "  ";
                } else {
                    cout << "-  ";
                }
            }
            cout << endl;
        }
    }

private:
    int num_vertex;
    int num_edge;
    T* vertex;
    TWeight** edge;
    TWeight no_edge_value; /* 表述没有边时的权重值 */
    bool directed; /* true为有向图，false为无向图 */
};